#!/usr/bin/env python
#
# http://en.wikipedia.org/wiki/Shell_sort
#

import math

a = [ 4,7,1,9,6,3,12,23,13,2,43,36 ]
print "Unsort",a
n = len(a)
inc = int(round(n/2))
temp, i, j = 0, 0, 0

while inc >0:
    for i in range(inc, n ):
        temp = a[i]
        j = i
        while j >= inc and a[j-inc] > temp:
            a[j] = a[j-inc]
            j = j-inc
        a[j] = temp
    inc = int(round(inc/2.2))

print "Sorted",a
